package nl.rug.jvleusen.datastructurelib;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import nl.rug.jvleusen.datastructurelib.graph.WeightedDirectionalGraph;
import nl.rug.jvleusen.datastructurelib.graph.WeightedUndirectionalGraph;

/**
 * This class implements the {@link IGraph} interface and adds methods and
 * implementation for weighted graphs, including an implementation of Dijkstra's
 * shortest path algorithm.
 *
 * @author Jeroen van Leusen
 * @see IGraph
 * @see WeightedDirectionalGraph
 * @see WeightedUndirectionalGraph
 */
public abstract class AbstractWeightedGraph<E, P extends AbstractWeightedGraph.Vertex<E, P>> implements IGraph<E> {

    /**
     * {@inheritDoc} This is extended by calling {@link AbstractWeightedGraph#add(java.lang.Object, java.lang.Object, int)}
     * with weight 1.
     */
    public boolean add(E x, E y) {
        return add(x, y, 1);
    }

    /**
     * Method added for the weighted graph, adds an edge with a specified
     * weight, does not change the weight if the edge already exists, use {@link AbstractWeightedGraph#setEdgeWeight(java.lang.Object, java.lang.Object, int)}
     * for that.
     *
     * @param x First item.
     * @param y Second item.
     * @param weight Edge weight to initialize on.
     * @return Whether the graph changed as a result of this method.
     */
    public abstract boolean add(E x, E y, int weight);

    /**
     * Method to retrieve the edge weight of a specified edge.
     *
     * @param x First item of the edge
     * @param y Second item of the edge
     * @return The weight of the specified edge, return -1 if there is no such
     * edge.
     */
    public abstract int getEdgeWeight(E x, E y);

    /**
     * Sets the weight of an edge to the specified weight, returns false if the
     * edge cannot be found or if the weight was already the specified amount.
     *
     * @param x First vertex
     * @param y Second vertex
     * @param weight Weight to set the edge to.
     * @return Whether it successfully set the edge, in practice this means
     * whether it has managed to find the edge in question and the weight
     * actually differed
     * @throws IllegalArgumentException For invalid weights.
     */
    public abstract boolean setEdgeWeight(E x, E y, int weight);

    /**
     * Evaluates and finds the length of the shortest path according to
     * Dijkstra's algorithm, it will return a path-length of -1 if there is no
     * valid path from the source to the target.
     *
     * To retrieve the actual sequence of vertices to get to the path, invoke {@link AbstractWeightedGraph#dijkstraPath(java.lang.Object, java.lang.Object)}
     * with the same parameters after this operation to retrieve a list.
     *
     * @param source The source vertex.
     * @param target The target vertex.
     * @return The length of the shortest path between source and target, will
     * return -1 if there is no path from source to target.
     * @throws IllegalArgumentException If a source is specified that is not
     * part of this graph.
     */
    public int dijkstra(E source, E target) {
        for (P vertex : getVertices()) {
            vertex.distance = Integer.MAX_VALUE;
            vertex.previousVertex = null;
        }
        P newSource = getVertex(source);

        if (newSource == null) {
            throw new IllegalArgumentException("Source is not part of this graph.");
        }

        newSource.distance = 0;

        PriorityQueue<P> queue = new PriorityQueue<P>();
        queue.add(newSource);

        while (!queue.isEmpty()) {
            P u = queue.poll();
            if (u.distance == Integer.MAX_VALUE || u.getData().equals(target)) {
                break;
            }

            for (P v : getNeighbors(u)) {
                int dist = u.distance + getEdgeWeight(u.getData(), v.getData());
                if (dist < v.distance) {
                    v.distance = dist;
                    v.previousVertex = u;
                    queue.add(v);
                }
            }
        }

        queue.clear();

        P targetVertex = getVertex(target);

        if (targetVertex == null || targetVertex.distance == Integer.MAX_VALUE) {
            return -1;
        } else {
            return targetVertex.distance;
        }
    }

    /**
     * Retrieves the sequence of vertices that build up a successfully completed
     * dijkstra's path, will return null if {@link AbstractWeightedGraph#dijkstra(java.lang.Object, java.lang.Object)}
     * isn't first called, or if said call returned -1
     *
     * @param source The source vertex.
     * @param target The target vertex.
     * @return The sequence of vertices that constitute the shortest path from
     * source to target.
     */
    public List<E> dijkstraPath(E source, E target) {
        P vSource = getVertex(source);
        P vTarget = getVertex(target);
        if (vSource == null || vTarget == null || vSource.distance != 0 || vTarget.distance == Double.POSITIVE_INFINITY) {
            return null; //there is no path to return.
        }

        P u = vTarget;
        List<E> path = new ArrayList<E>();

        do {
            path.add(u.getData());
            u = u.previousVertex;
        } while (u != null);

        Collections.reverse(path);

        return path;
    }

    /*
     * Internal methods for dijkstra.
     */
    /**
     * Gets a list of all vertices within this graph.
     *
     * @return A list of vertices.
     */
    protected abstract List<P> getVertices();

    /**
     * This should return the vertex belonging to the specified data.
     *
     * @param data Data to match a vertex to.
     * @return The vertex, null if there is none.
     */
    protected abstract P getVertex(E data);

    /**
     * Get a list of the vertices that can be reached directly from the
     * specified vertex.
     *
     * @param vertex The vertex to evaluate.
     * @return A list containing the neighbors of the specified vertex within
     * this graph, return null if the vertex doesn't exist.
     */
    protected abstract List<P> getNeighbors(P vertex);

    /*
     * Any implementation of this class should provide an extension of this
     * class, it provides the methods and fields required for dijksta's
     * algorithm
     */
    public static abstract class Vertex<E, P extends AbstractWeightedGraph.Vertex<E, P>> implements Comparable<P> {

        protected int distance;
        protected P previousVertex;

        public abstract E getData();

        //Comparator for the PriorityQueue
        public int compareTo(P other) {
            return Integer.compare(distance, other.distance);
        }
    }
}
